/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package hu.arguscab.ai;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;


/**
 * &nbsp&nbsp&nbsp A       Order of the iteration is: A, B, C, D, E, F, G<br>
 *&nbsp&nbsp/ &nbsp \<br>
 *&nbspB &nbsp &nbsp &nbspC<br>
 * / \ &nbsp &nbsp/ &nbsp\<br>
 *     D&nbsp&nbspE&nbsp&nbspF  G<br>
 * @param <E> The data type that <code>Edge</code> contain. 
 * @param <N> The data type that <code>Node</code> contain. 
 * @author sharp
 */
public class BreadthSearchIterator<E, N> extends GraphIterable<E, N>{

	Node<N> root;
	public BreadthSearchIterator(Graph<E, N> g, Node<N> root) {
		super(g);
		this.root = root;
	}

	public Iterator<Node<N>> iterator() {
		return new BreadthSearchIteratorImpl<E, N>(getGraph(), root);
	}
}

class BreadthSearchIteratorImpl<E, N> extends GraphIterator<E, N> {

	Queue<Node<N>> list = new LinkedList<Node<N>>();
	Set<Node<N>> closedList = new HashSet<Node<N>>();

	public BreadthSearchIteratorImpl(Graph<E, N> g, Node<N> root) {
		super(g);
		list.add(root);
	}

	public boolean hasNext() {
		return list.size() > 0;
	}

	public Node<N> next() {
		// itt történik a kifejtés
		Node<N> returnNode = list.poll();

		for ( Node<N> child : getGraph().adjacentTo(returnNode) ) {
			if ( closedList.contains(child) == false ) {
				list.add(child);
				closedList.add(child);
			}
		}

		return returnNode;
	}

	public void remove() {
		throw new UnsupportedOperationException("Not supported yet.");
	}
}
